package com.salim.leetcode.$145;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreePostorderTraversal {
    //树的后序遍历-> 左 右 根 要求使用迭代
    //先一直入栈左
    //如果碰到节点左右都没有 记录结果
    //回退到有右节点的根
    //push右节点
    //重复
    //只有左右都没有的时候才记录
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current;
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            current = stack.peek();
            if(current.left!=null){
                stack.push(current.left);
            }else if(current.right!=null){
                stack.push(current.right);
            }else{
                //回退到有右节点的根
                while(!stack.isEmpty()&& stack.peek().left==null && stack.peek().right==null){
                    current = stack.pop();
                    result.add(current.val);
                    if(!stack.isEmpty()){
                        if(stack.peek().left == current){
                            stack.peek().left = null;
                        }else if(stack.peek().right == current){
                            stack.peek().right = null;
                        }
                    }
                }
                if(!stack.isEmpty() && stack.peek().right!=null){
                    stack.push(stack.peek().right);
                }
            }
        }
        return result;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
